In compiling a source program written in a high level language to target program written in a low level language, optimizing compilers perform certain optimizing transformations. Such transformations are applied to an intermediate program representation of the source program in an intermediate language. One such transformation includes algebraic simplification wherein complex expressions in the intermediate program representation are replaced with simpler expressions. Optimizing compilers perform algebraic simplification using a term rewriting system which embodies a set of rules defining conditions under which matched terms in the intermediate program representation may be replaced.
A problem with such term rewriting systems occurs when an expression in the intermediate program representation feeds several others using assignments to variables. For example, consider the following simple program:a=b+c; if(n<10)d=a−b;elsee=a−c;
This program may be simplified so that the assignments to d become d=c and the assignment to e becomes e=b. That this simplification is possible is evident when the program is transformed as follows:d=(b+c)−b;elsee=(b+c)−c;
Assuming the term rewriting system uses rules such as(X+Y)−X→Y(X+Y)−Y→XThen it is apparent that these rules are applicable once variable “a” has been eliminated by substitution of its right hand side into its uses. The problem in the above example is that in order to trigger the term rewriting rules the program would have to be transformed as described. This could be achieved by performing a comprehensive forward substitution in which variables in the right hand side of expressions are replaced with the full sub expressions. Performing such a comprehensive forward substitution prior to rewriting would enlarge trees seen by the rewriting system making it impractical. Moreover, such a comprehensive forward substitution does not address whether the term rewriting rules would in fact apply after forward substitution, resulting in redundant computation in some cases with no benefit.